{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 第2章 感知机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 习题2.1\n",
    "&emsp;&emsp;Minsky 与 Papert 指出：感知机因为是线性模型，所以不能表示复杂的函数，如异或 (XOR)。验证感知机为什么不能表示异或。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**  \n",
    "1. 列出异或函数(XOR)的输入和输出；\n",
    "2. 使用图例法证明异或问题是线性不可分的；\n",
    "3. 使用反证法证明感知机无法表示异或。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解题步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：异或函数(XOR)的输入和输出**\n",
    "\n",
    "&emsp;&emsp;对于异或函数(XOR)，全部的输入与对应的输出如下：  \n",
    "\n",
    "|<div style=\"width:20px\">$x_1$</div>|<div style=\"width:20px\">$x_2$</div>|<div style=\"width:92px\">$y=x_1\\oplus x_2$</div>|\n",
    "|:-: | :-: | :-: |  \n",
    "| 0 | 0 | -1 | \n",
    "| 0 | 1 | 1 | \n",
    "| 1 | 0 | 1 | \n",
    "| 1 | 1 | -1 | "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：使用图例法证明异或问题是线性不可分的**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>x1</th>\n",
       "      <th>x2</th>\n",
       "      <th>y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   x1  x2  y\n",
       "0   0   0 -1\n",
       "1   0   1  1\n",
       "2   1   0  1\n",
       "3   1   1 -1"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# 使用Dataframe表示异或的输入与输出数据\n",
    "x1 = [0, 0, 1, 1]\n",
    "x2 = [0, 1, 0, 1]\n",
    "y = [-1, 1, 1, -1]\n",
    "x1 = np.array(x1)\n",
    "x2 = np.array(x2)\n",
    "y = np.array(y)\n",
    "data = np.c_[x1, x2, y]\n",
    "data = pd.DataFrame(data, index=None, columns=['x1', 'x2', 'y'])\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZIAAAEKCAYAAAA4t9PUAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAVN0lEQVR4nO3df3BV5Z3H8c+XEJqEHxXBbbHRwOwwSwFDDAnS+mOIoxCsI4xVkGFK6+hcCzq2U7cjXQZwYWVcZbYO4gLpatGaVlJ/VNoFpdRUseA0oY2sUlrQFczgVgga0QiCfPePc4kJhJDkuTcnP96vmcy55znPOed7z9zJZ8459zzX3F0AAHRUn7gLAAB0bwQJACAIQQIACEKQAACCECQAgCAECQAgSKxBYmaPmtl7Zvb6GZZPMrN6M6tJ/i3q7BoBAK3rG/P+10paKenxVvpscfdrO6ccAEB7xXpG4u4vSzoUZw0AgDBxn5G0xdfM7DVJ+yX9s7u/0VInM0tISkhS//79x48aNaoTSwSA7m379u0H3f28jqzb1YPkT5Ly3P0jM7tG0q8kjWypo7uXSSqTpKKiIq+uru60IgGguzOzvR1dt0t/a8vdP3T3j5KvN0jKNLOhMZcFAGiiSweJmX3ZzCz5eoKieuvirQoA0FSsl7bM7BeSJkkaama1khZLypQkd18t6QZJc83suKRPJN3kDFcMAF1KrEHi7rPOsnyloq8HA0CjY8eOqba2VkeOHIm7lG4nKytLubm5yszMTNk2u/rNdgA4TW1trQYOHKjhw4crefUbbeDuqqurU21trUaMGJGy7XbpeyQA0JIjR45oyJAhhEg7mZmGDBmS8jM5ggRAt0SIdEw6jhtBAgAIQpAAQDtlZGSooKBAY8eO1Y033qiGhoZ2rb9//37dcMMNkqSamhpt2LChcdn69et13333pbTedCNIAPR85eXS8OFSnz7RtLw8aHPZ2dmqqanR66+/rn79+mn16tXtWv/888/XU089Jen0ILnuuus0f/78oPo6G0ECoGcrL5cSCWnvXsk9miYSwWFy0uWXX649e/bo0KFDmj59uvLz8zVx4kTt2LFDkvTSSy+poKBABQUFuvjii3X48GG9/fbbGjt2rD799FMtWrRI69atU0FBgdatW6e1a9fqjjvuUH19vYYPH64TJ05IkhoaGnTBBRfo2LFjevPNN1VaWqrx48fr8ssv165du1LyXjqKIAHQsy1YIJ166amhIWoPdPz4cW3cuFEXXXSRFi9erIsvvlg7duzQsmXLNGfOHEnS8uXL9fDDD6umpkZbtmxRdnZ24/r9+vXTkiVLNHPmTNXU1GjmzJmNy774xS9q3LhxeumllyRJv/71rzVlyhRlZmYqkUjooYce0vbt27V8+XLNmzcv+L2E4DkSAD3bvn3ta2+DTz75RAUFBZKiM5JbbrlFl1xyiZ5++mlJ0pVXXqm6ujrV19fr0ksv1Q9+8APNnj1b119/vXJzc9u8n5kzZ2rdunUqKSnRk08+qXnz5umjjz7S1q1bdeONNzb2O3r0aIffSyoQJAB6tgsvjC5ntdTeQSfvkTTV0uhNZqb58+frG9/4hjZs2KCJEydq8+bNysrKatN+rrvuOv3oRz/SoUOHtH37dl155ZX6+OOPdc4555y2/zhxaQtAz3bvvVJOTvO2nJyoPYWuuOIKlSfvu/z+97/X0KFDNWjQIL355pu66KKLdPfdd6uoqOi0+xkDBw7U4cOHW9zmgAEDNGHCBH3ve9/Ttddeq4yMDA0aNEgjRozQL3/5S0lRgL322mspfS/tRZAA6Nlmz5bKyqS8PMksmpaVRe0pdM8996i6ulr5+fmaP3++HnvsMUnSgw8+qLFjx2rcuHHKzs7W1KlTm61XUlKinTt3Nt5sP9XMmTP1xBNPNLt/Ul5erkceeUTjxo3TmDFj9Nxzz6X0vbSX9cTBdPlhK6Bn+8tf/qKvfvWrcZfRbbV0/Mxsu7sXdWR7nJEAAIIQJACAIAQJACAIQQIACEKQAACCECQAgCAECQC0k5nprrvuapxfvny57rnnnpTvZ9myZc3mv/71r6d8H6lAkADo0e6/X6qsbN5WWRm1d9QXvvAFPfPMMzp48GBYcWdxapBs3bo1rfvrKIIEQI9WXCzNmPF5mFRWRvPFxR3fZt++fZVIJPTjH//4tGUHDhzQN7/5TRUXF6u4uFh/+MMfGtuvvvpqFRYW6rbbblNeXl5jEE2fPl3jx4/XmDFjVFZWJkmaP39+4+CQs5NP4Q8YMEBS9LR7098w+c53vqOnn35an332mX74wx+quLhY+fn5WrNmTcffZHu4e4/7Gz9+vAPouXbu3Nmu/i++6D50qPvChdH0xRfD9t+/f3+vr6/3vLw8/+CDD/yBBx7wxYsXu7v7rFmzfMuWLe7uvnfvXh81apS7u99+++2+bNkyd3ffuHGjS/IDBw64u3tdXZ27uzc0NPiYMWP84MGDjfs5db/u7s8884zPmTPH3d2PHj3qubm53tDQ4GvWrPGlS5e6u/uRI0d8/Pjx/tZbb51Wf0vHT1K1d/B/LqP/AujxSkqkuXOlpUulhQuj+VCDBg3SnDlztGLFima/MbJ582bt3Lmzcf7DDz/U4cOH9corr+jZZ5+VJJWWlmrw4MGNfVasWNG47J133tHu3bs1ZMiQM+576tSpuvPOO3X06FE9//zzuuKKK5Sdna1NmzZpx44djb++WF9fr927d2vEiBHhb7gVBAmAHq+yUlq1KgqRVauiIElFmHz/+99XYWGhbr755sa2EydOaNu2bc3CRWp5mHkpGil48+bN2rZtm3JycjRp0iQdOXKk1f1mZWVp0qRJeuGFF7Ru3TrNmjWrcR8PPfSQpkyZEvjO2od7JAB6tJP3RCoqpCVLomnTeyYhzj33XM2YMUOPPPJIY9vkyZO1cuXKxvmTvxty2WWXqaKiQpK0adMmvf/++5Kis4bBgwcrJydHu3bt0quvvtq4bmZmpo4dO9bivm+66Sb99Kc/1ZYtWxqDY8qUKVq1alXjOn/729/08ccfh7/RsyBIAPRoVVVReJw8AykpiearqlKz/bvuuqvZt7dWrFjROJz86NGjtXr1aknS4sWLtWnTJhUWFmrjxo0aNmyYBg4cqNLSUh0/flz5+flauHChJk6c2LitRCKh/Pz8xpvtTU2ePFkvv/yyrrrqKvXr10+SdOutt2r06NEqLCzU2LFjddttt+n48eOpeaOtYBh5AN1OdxxG/ujRo8rIyFDfvn21bds2zZ07N7ZfOUz1MPLcIwGATrBv3z7NmDFDJ06cUL9+/fSTn/wk7pJShiABgE4wcuRI/fnPf467jLTgHgmAbqknXpbvDOk4bgQJgG4nKytLdXV1hEk7ubvq6uqUlZWV0u1yaQtAt5Obm6va2lodOHAg7lK6naysLOXm5qZ0mwQJgG4nMzMz7U9ro+24tAUACEKQAACCECQAgCAECQAgCEECAAhCkAAAghAkAIAgBAkAIAhBAgAIQpAAAIIQJACAIAQJACBIrEFiZo+a2Xtm9voZlpuZrTCzPWa2w8wKO7vGXqu8XBo+XOrTJ5qWl8ddESBJuv9+qbKyeVtlZdSOeMR9RrJWUmkry6dKGpn8S0ha1Qk1obxcSiSkvXsl92iaSBAm6BKKi6UZMz4Pk8rKaL64ON66erNYg8TdX5Z0qJUu0yQ97pFXJZ1jZsM6p7pebMECqaGheVtDQ9QOxKykRKqoiMJj0aJoWlERtSMecZ+RnM1XJL3TZL422XYaM0uYWbWZVfNjN4H27WtfO9DJSkqkuXOlpUujKSESr64eJNZCW4u/renuZe5e5O5F5513XprL6uEuvLB97UAnq6yUVq2SFi6MpqfeM0Hn6upBUivpgibzuZL2x1RL73HvvVJOTvO2nJyoHYjZyXsiFRXSkiWfX+YiTOLT1YNkvaQ5yW9vTZRU7+7vxl1Ujzd7tlRWJuXlSWbRtKwsagdiVlXV/J7IyXsmVVXx1tWbmXuLV4o6Z+dmv5A0SdJQSX+XtFhSpiS5+2ozM0krFX2zq0HSze5efbbtFhUVeXX1WbsBAJLMbLu7F3Vk3b6pLqY93H3WWZa7pNs7qRwAQAd09UtbAIAujiABAAQhSAAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABCEIAEABCFIAABBCBIAQBCCBAAQhCABAAQhSAAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABCEIAEABCFIAABBCBIAQBCCBAAQhCABAAQhSAAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABCEIAEABCFIAABBCBIAQBCCBAAQhCABAAQhSAAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABCk1SAxs0Fm9o8ttOenryQAQHdyxiAxsxmSdkl62szeMLPiJovXprswAED30NoZyb9IGu/uBZJulvQzM7s+uczSXRgAoHvo28qyDHd/V5Lc/Y9mViLpN2aWK8k7pToAQJfX2hnJ4ab3R5KhMknSNElj0lwXAKCbaC1I5krqY2ajTza4+2FJpZJuTXdhAIDu4YxB4u6vuftuSRVmdrdFsiX9h6R5nVYhAKBLa8tzJJdIukDSVklVkvZLujSdRQEAuo+2BMkxSZ9IypaUJel/3f1EWqsCAHQbbQmSKkVBUizpMkmzzOyptFYFAOg2Wvv670m3uHt18vX/SZpmZt9KY00AgG7krGckTUKkadvP0lMOAKC7YdBGAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABCEIAEABCFIAABBCBIAQBCCBAAQhCABAAQhSAAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABCEIAEABCFIAABBCBIAQBCCBAAQhCABAAQhSAAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABCEIAEABCFIAABBCBIAQBCCBAAQhCABAAQhSAAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABAk1iAxs1Iz+6uZ7TGz+S0sNzNbkVy+w8wK46izt7n/fqmysnlbZWXUDnQJ5eXS8OFSnz7RtLw87op6tdiCxMwyJD0saaqk0ZJmmdnoU7pNlTQy+ZeQtKpTi+ylioulGTM+D5PKymi+uDjeugBJUWgkEtLevZJ7NE0kCJMYxXlGMkHSHnd/y90/lfSkpGmn9Jkm6XGPvCrpHDMb1tmF9jYlJVJFRRQeixZF04qKqB2I3YIFUkND87aGhqgdsYgzSL4i6Z0m87XJtvb2kSSZWcLMqs2s+sCBAykttDcqKZHmzpWWLo2mhAi6jH372teOtIszSKyFNu9An6jRvczdi9y96LzzzgsurrerrJRWrZIWLoymp94zAWJz4YXta0faxRkktZIuaDKfK2l/B/ogxU7eE6mokJYs+fwyF2GCLuHee6WcnOZtOTlRO2IRZ5BUSRppZiPMrJ+kmyStP6XPeklzkt/emiip3t3f7exCe5uqqub3RE7eM6mqircuQJI0e7ZUVibl5Ulm0bSsLGpHLMy9xStFnbNzs2skPSgpQ9Kj7n6vmX1Xktx9tZmZpJWSSiU1SLrZ3avPtt2ioiKvrj5rNwBAkpltd/eijqzbN9XFtIe7b5C04ZS21U1eu6TbO7suAEDb8WQ7ACAIQQIACEKQAACCECQAgCAECQAgCEECAAhCkAAAghAkAIAgBAkAIAhBAgAIQpAAAIIQJACAIAQJACAIQQIACEKQAACCECQAgCAECQAgCEECAAhCkAAAghAkAIAgBAkAIAhBAgAIQpAAAIIQJACAIAQJACAIQQIACEKQAACCECQAgCAECQAgCEECAAhCkAAAghAkAIAgBAkAIAhBAgAIQpAAAIIQJACAIAQJACAIQQIACEKQAACCECQAgCAECQAgCEECAAhCkAAAghAkAIAgBAkAIAhBAgAI0jeOnZrZuZLWSRou6W1JM9z9/Rb6vS3psKTPJB1396LOqxIA0BZxnZHMl/Q7dx8p6XfJ+TMpcfcCQgQAuqa4gmSapMeSrx+TND2mOgAAgWK5tCXpS+7+riS5+7tm9g9n6OeSNpmZS1rj7mVn2qCZJSQlkrNHzez1lFbcew2VdDDuIoAz4POZOv/U0RXTFiRmtlnSl1tYtKAdm7nU3fcng+a3ZrbL3V9uqWMyZMqS+67mUlhqcCzRlfH5TB0zq+7oumkLEne/6kzLzOzvZjYseTYyTNJ7Z9jG/uT0PTN7VtIESS0GCQAgHnHdI1kv6dvJ19+W9NypHcysv5kNPPla0mRJXK4CgC4mriC5T9LVZrZb0tXJeZnZ+Wa2IdnnS5JeMbPXJP1R0n+7+/Nt3P4Z76Wg3TiW6Mr4fKZOh4+luXsqCwEA9DI82Q4ACEKQAACCdPsgMbNzzey3ZrY7OR18hn5vm9n/mFlNyNfceiozKzWzv5rZHjM7baQBi6xILt9hZoVx1Inex8weNbP3zvRsGJ/NtmvDsZxkZvXJ/5M1ZraoLdvt9kEihlsJZmYZkh6WNFXSaEmzzGz0Kd2mShqZ/EtIWtWpRaI3WyuptJXlfDbbbq1aP5aStCX5f7LA3Ze0ZaM9IUgYbiXcBEl73P0td/9U0pOKjmtT0yQ97pFXJZ2TfAYISKvkQ8iHWunCZ7ON2nAsO6QnBEmz4VYknW24le3J4VTwua9IeqfJfG2yrb19gDjw2Uytr5nZa2a20czGtGWFuMbaapfOHm6lF7IW2k79Xnhb+gBx4LOZOn+SlOfuH5nZNZJ+peiSYau6RZAw3Era1Uq6oMl8rqT9HegDxIHPZoq4+4dNXm8ws/80s6Hu3urAmD3h0hbDrYSrkjTSzEaYWT9JNyk6rk2tlzQn+Q2ZiZLqT15SBGLGZzNFzOzLZmbJ1xMUZUTd2dbrFmckZ3GfpAozu0XSPkk3StFwK5L+y92vUTTcyrPJ49NX0s/bMdxKj+fux83sDkkvSMqQ9Ki7v2Fm300uXy1pg6RrJO2R1CDp5rjqRe9iZr+QNEnSUDOrlbRYUqbEZ7O92nAsb5A018yOS/pE0k3ehuFPGCIFABCkJ1zaAgDEiCABAAQhSAAAQQgSAEAQggQAEIQgATqRmT1vZh+Y2W/irgVIFYIE6FwPSPpW3EUAqUSQAGlgZsXJ38bISo6s8IaZjXX330k6HHd9QCr1hCfbgS7H3avMbL2kf5OULekJd2dYHvRIBAmQPksUjWN2RNKdMdcCpA2XtoD0OVfSAEkDJWXFXAuQNgQJkD5lkhZKKpf07zHXAqQNl7aANDCzOZKOu/vPzSxD0lYzu1LSv0oaJWlAcvTVW9z9hThrBUIx+i8AIAiXtgAAQQgSAEAQggQAEIQgAQAEIUgAAEEIEgBAEIIEABDk/wEN/5+6mW6xxQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 获取正类别（y=1）的数据\n",
    "positive = data.loc[data['y'] == 1]\n",
    "# 获取负类别（y=-1）的数据\n",
    "negative = data.loc[data['y'] == -1]\n",
    "\n",
    "# 绘制数据图\n",
    "# 绘制坐标轴\n",
    "plt.xlim(-0.5, 1.5)\n",
    "plt.ylim(-0.5, 1.5)\n",
    "plt.xticks([-0.5, 0, 1, 1.5])\n",
    "plt.yticks([-0.5, 0, 1, 1.5])\n",
    "# 添加坐标轴文字\n",
    "plt.xlabel(\"x1\")\n",
    "plt.ylabel(\"x2\")\n",
    "# 绘制正、负样本点\n",
    "plt.plot(positive['x1'], positive['x2'], \"ro\")\n",
    "plt.plot(negative['x1'], negative['x2'], \"bx\")\n",
    "# 添加图示\n",
    "plt.legend(['Positive', 'Negative'])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;从上图可以看出，无法使用一条直线将两类样本分开，所以异或问题是线性不可分的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "感知机模型的参数：w= [0. 0.] b= 0.0\n"
     ]
    }
   ],
   "source": [
    "from sklearn.linear_model import Perceptron\n",
    "import numpy as np\n",
    "\n",
    "# 构造异或问题的训练数据集\n",
    "X_train = np.array([[1, 1], [1, 0], [0, 1], [0, 0]])\n",
    "y = np.array([-1, 1, 1, -1])\n",
    "\n",
    "# 使用sklearn的Perceptron类构建感知机模型\n",
    "perceptron_model = Perceptron()\n",
    "# 进行模型训练\n",
    "perceptron_model.fit(X_train, y)\n",
    "\n",
    "# 打印模型参数\n",
    "print(\"感知机模型的参数：w=\", perceptron_model.coef_[\n",
    "      0], \"b=\", perceptron_model.intercept_[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;上述使用sklearn的Perceptron类构建感知机模型，从模型的参数上观察，感知机模型无法表示异或。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第3步：使用反证法证明感知机无法表示异或**\n",
    "\n",
    "&emsp;&emsp;根据书中第35页感知机模型的定义：  \n",
    "> **定义2.1（感知机）** 假设输入空间（特征空间）是$\\mathcal{X} \\subseteq R^n$，输出空间是$\\mathcal{y}=\\{+1,-1\\}$。输入$x \\in \\mathcal{X}$表示实例的特征向量，对应于输入空间（特征空间）的点；输出$y \\in \\mathcal{Y}$表示实例的类别。由输入空间到输出空间的如下函数：\n",
    "> $$\n",
    "f(x)=\\text{sign}(w \\cdot x + b)\n",
    "$$\n",
    "> 称为感知机。其中，$w$和$b$为感知机模型参数，$w \\in R^n$叫做权值或权值向量，$b \\in R$叫做偏置，$w \\cdot x$表示$w$和$x$的内积。sign是符号函数，即\n",
    "> $$\n",
    "\\text{sign}(x)=\\left \\{ \\begin{array}{ll}\n",
    "+1, \\quad x \\geqslant 0 \\\\\n",
    "-1, \\quad x < 0\n",
    "\\end{array}\\right.\n",
    "$$\n",
    "\n",
    "&emsp;&emsp;假设感知机模型可以表示异或问题，即满足异或函数(XOR)输入与输出的情况（见**第1步**）。假设$x$向量只有两个维度$x_1$，$x_2$：\n",
    "1. 根据$x_1=0, x_2=0, f(x)=-1$，则$w \\cdot x +b < 0$，可得$b < 0$；\n",
    "2. 根据$x_1=0, x_2=1, f(x)=1$，则$w_2 + b > 0$，结合$b < 0$，可得$w_2 > -b > 0$；\n",
    "3. 根据$x_1=1, x_2=0, f(x)=1$，则$w_1 + b > 0$，结合$b < 0$，可得$w_1 > -b > 0$；\n",
    "4. 根据$x_1=1, x_2=1$，并结合$w_1 + b > 0$、$w_2 > 0$，则$w_1 + w_2 + b > 0$，可得$f(x)=1$，与异或条件中的$f(x)=-1$矛盾。\n",
    "\n",
    "&emsp;&emsp;所以假设不成立，原命题成立，即感知机模型不能表示异或。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题2.2\n",
    "\n",
    "&emsp;&emsp;模仿例题 2.1，构建从训练数据求解感知机模型的例子。\n",
    "\n",
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**  \n",
    "&emsp;&emsp;按照书中第38~39页感知机学习算法2.1，编写代码并绘制分离超平面\n",
    "> 算法2.1（感知机学习算法的原始形式）  \n",
    "输入：训练数据集$T=\\{(x_1,y_1),(x_2,y_2),\\ldots,(x_N,y_N)\\}$，其中$x_i \\in \\mathcal{X} = R^n$，$y_i \\in \\mathcal{Y} = \\{-1, +1\\}$，$i=1,2,\\ldots,N$；学习率$\\eta (0 < \\eta \\leqslant 1)$；  \n",
    "输出：$w,b$；感知机模型$f(x)=\\text{sign}(w \\cdot x + b)$  \n",
    "（1）选取初值$w_0, b_0$；  \n",
    "（2）在训练集中选取数据$(x_i,y_i)$；  \n",
    "（3）如果$y_i(w \\cdot x_i + b) \\leqslant 0$，\n",
    "> $$\n",
    "\\begin{array}{ll}\n",
    "w \\leftarrow w + \\eta y_i x_i \\\\\n",
    "b \\leftarrow b + \\eta y_i\n",
    "\\end{array}\n",
    "$$  \n",
    ">（4）转至（2），直至训练集中没有误分类点。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解题步骤：**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "%matplotlib tk\n",
    "\n",
    "\n",
    "class Perceptron:\n",
    "    def __init__(self, X, Y, lr=0.001, plot=True):\n",
    "        \"\"\"\n",
    "        初始化感知机\n",
    "        :param X: 特征向量\n",
    "        :param Y: 类别\n",
    "        :param lr: 学习率\n",
    "        :param plot: 是否绘制图形\n",
    "        \"\"\"\n",
    "        self.X = X\n",
    "        self.Y = Y\n",
    "        self.lr = lr\n",
    "        self.plot = plot\n",
    "        if plot:\n",
    "            self.__model_plot = self._ModelPlot(self.X, self.Y)\n",
    "            self.__model_plot.open_in()\n",
    "\n",
    "    def fit(self):\n",
    "        # (1)初始化weight, b\n",
    "        weight = np.zeros(self.X.shape[1])\n",
    "        b = 0\n",
    "        # 训练次数\n",
    "        train_counts = 0\n",
    "        # 分类错误标识\n",
    "        mistake_flag = True\n",
    "        while mistake_flag:\n",
    "            # 开始前，将mistake_flag设置为False，用于判断本次循环是否有分类错误\n",
    "            mistake_flag = False\n",
    "            # (2)从训练集中选取x,y\n",
    "            for index in range(self.X.shape[0]):\n",
    "                if self.plot:\n",
    "                    self.__model_plot.plot(weight, b, train_counts)\n",
    "                # 损失函数\n",
    "                loss = self.Y[index] * (weight @ self.X[index] + b)\n",
    "                # (3)如果损失函数小于0，则该点是误分类点\n",
    "                if loss <= 0:\n",
    "                    # 更新weight, b\n",
    "                    weight += self.lr * self.Y[index] * self.X[index]\n",
    "                    b += self.lr * self.Y[index]\n",
    "                    # 训练次数加1\n",
    "                    train_counts += 1\n",
    "                    print(\"Epoch {}, weight = {}, b = {}, formula: {}\".format(\n",
    "                        train_counts, weight, b, self.__model_plot.formula(weight, b)))\n",
    "                    # 本次循环有误分类点（即分类错误），置为True\n",
    "                    mistake_flag = True\n",
    "                    break\n",
    "        if self.plot:\n",
    "            self.__model_plot.close()\n",
    "        # (4)直至训练集中没有误分类点\n",
    "        return weight, b\n",
    "\n",
    "    class _ModelPlot:\n",
    "        def __init__(self, X, Y):\n",
    "            self.X = X\n",
    "            self.Y = Y\n",
    "\n",
    "        @staticmethod\n",
    "        def open_in():\n",
    "            # 打开交互模式，用于展示动态交互图\n",
    "            plt.ion()\n",
    "\n",
    "        @staticmethod\n",
    "        def close():\n",
    "            # 关闭交互模式，并显示最终的图形\n",
    "            plt.ioff()\n",
    "            plt.show()\n",
    "\n",
    "        def plot(self, weight, b, epoch):\n",
    "            plt.cla()\n",
    "            # x轴表示x1\n",
    "            plt.xlim(0, np.max(self.X.T[0]) + 1)\n",
    "            # y轴表示x2\n",
    "            plt.ylim(0, np.max(self.X.T[1]) + 1)\n",
    "            # 画出散点图，并添加图示\n",
    "            scatter = plt.scatter(self.X.T[0], self.X.T[1], c=self.Y)\n",
    "            plt.legend(*scatter.legend_elements())\n",
    "            if True in list(weight == 0):\n",
    "                plt.plot(0, 0)\n",
    "            else:\n",
    "                x1 = -b / weight[0]\n",
    "                x2 = -b / weight[1]\n",
    "                # 画出分离超平面\n",
    "                plt.plot([x1, 0], [0, x2])\n",
    "                # 绘制公式\n",
    "                text = self.formula(weight, b)\n",
    "                plt.text(0.3, x2 - 0.1, text)\n",
    "            plt.title('Epoch %d' % epoch)\n",
    "            plt.pause(0.01)\n",
    "\n",
    "        @staticmethod\n",
    "        def formula(weight, b):\n",
    "            text = 'x1 ' if weight[0] == 1 else '%d*x1 ' % weight[0]\n",
    "            text += '+ x2 ' if weight[1] == 1 else (\n",
    "                '+ %d*x2 ' % weight[1] if weight[1] > 0 else '- %d*x2 ' % -weight[1])\n",
    "            text += '= 0' if b == 0 else ('+ %d = 0' %\n",
    "                                          b if b > 0 else '- %d = 0' % -b)\n",
    "            return text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1, weight = [3. 3.], b = 1, formula: 3*x1 + 3*x2 + 1 = 0\n",
      "Epoch 2, weight = [2. 2.], b = 0, formula: 2*x1 + 2*x2 = 0\n",
      "Epoch 3, weight = [1. 1.], b = -1, formula: x1 + x2 - 1 = 0\n",
      "Epoch 4, weight = [0. 0.], b = -2, formula: 0*x1 - 0*x2 - 2 = 0\n",
      "Epoch 5, weight = [3. 3.], b = -1, formula: 3*x1 + 3*x2 - 1 = 0\n",
      "Epoch 6, weight = [2. 2.], b = -2, formula: 2*x1 + 2*x2 - 2 = 0\n",
      "Epoch 7, weight = [1. 1.], b = -3, formula: x1 + x2 - 3 = 0\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEICAYAAACktLTqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAomElEQVR4nO3deXgV9fn+8feTEAg7AkGWIItssi8BgVBrXVo3QBQtiKK4AAq2ta120Wq12tqf39pWQBH3BXEBwVAV91YDsgRkXxQQJewgq5gQwvP7I0fFEMhJcpJJzrlf1zUX58x8ZubJueDOMGfmGXN3REQkusQFXYCIiESewl1EJAop3EVEopDCXUQkCincRUSikMJdRCQKKdxFisDM3MxaBV2HSGEU7lJhmdkGM/vGzA4cNY0Puq5vmdnEfLVlm9n+oOuS2FAp6AJESqi/u78bdBEFcffRwOhv35vZ08CRwAqSmKIjd4lKZnaNmc02s3FmttfMVpvZ2Uctb2xmaWb2lZmtNbMbjloWb2Z/NLN1ZrbfzBaaWdOjNn+OmX1mZrvNbIKZWRj1VAcuBZ6J6A8qchw6cpdodjowFagPXAK8amYt3P0rYAqwAmgMtAPeMbP17v4e8GtgKHAB8CnQGTh41HYvAnoCtYCFwExgViG1XArsAD6MzI8mcmI6cpeKboaZ7TlquuGoZduBf7l7jru/BKwBLgwdhfcDfufuWe6+GHgcuCq03vXAHe6+xvMscfddR233fnff4+5fAh8AXcOo82rgWVczJykjOnKXiu7iE5xz35QvTL8g70i9MfCVu+/Ptywl9LopsO4E+9x61OuDQI0TFRj6ZfJj4IYTjROJJB25SzRrku98+CnA5tBU18xq5lu2KfR6I3BqBOsYDsxx9/UR3KbICSncJZo1AH5hZglmdhlwGvCGu28E5gB/M7NEM+sMXAdMDq33OPAXM2tteTqbWb0S1DEceLoE64sUmU7LSEU308xyj3r/jrsPCr2eB7QGdgLbgMFHnTsfCkwk7yh+N3CXu78TWvYgUAV4m7wvY1cD326zSMysD5AMvFKc9UWKy/T9jkQjM7sGuN7d+wVdi0gQdFpGRCQKhR3uoRs7PjGz/xSwzMzsodDNIEvNrHtkyxQRkaIoypH7L4FVx1l2PnnnNlsDI4FHSliXSIm4+9M6JSOxLKxwN7Nk4ELyriIoyEBCN2i4+1ygjpk1ilCNIiJSROFeLfMv4Dag5nGWNyHv2uBvZYbmbTl6kJmNJO/InurVq/do165dUWoVEYl5Cxcu3OnuSYWNKzTczewiYLu7LzSzM483rIB5x1yG4+6TgEkAKSkpnpGRUdjuRUTkKGb2RTjjwjktkwoMMLMNwIvAWWb2fL4xmeTdsv2tZPKuHxYRkQAUGu7u/gd3T3b35sAQ4H13vzLfsDRgeOiqmd7AXnffkn9bIiJSNop9h6qZjQZw94nAG+S1R11LXiOlERGpTkREiqVI4e7u/wX+G3o98aj5DoyJZGEiIkWVk5NDZmYmWVlZQZdSYomJiSQnJ5OQkFCs9dVbRkSiRmZmJjVr1qR58+aE8YCscsvd2bVrF5mZmbRo0aJY21D7ARGJGllZWdSrV69CBzuAmVGvXr0S/Q9E4S4iUaWiB/u3SvpzKNxFRKKQwl1EJAop3EVEopDCXUSkjF177bU0aNCAjh07lto+FO4iErPee+EjhjW/kZ/GX86w5jfy3gsflcl+r7nmGmbNmlWq+9B17iISk9574SP+OXIi2QcPAbD9y538c2TevZlnX/GjUt33GWecwYYNG0p1HzpyF5GY9OQfX/gu2L+VffAQT/7xhYAqiiwduYtITNqxcVeR5hfFOeecw9atW4+Zf9999zFw4MASbz8cCncRiUlJTeux/cudBc4vqXfffbfE2ygpnZYRkZh07V+voEq1yj+YV6VaZa796xUBVRRZCncRiUlnX/Ejbpk0mgan1MfMaHBKfW6ZNLrUv0wFGDp0KH369GHNmjUkJyfzxBNPRHwfOi0jIjHr7Ct+VCZhnt+UKVNKfR86chcRiUIKdxGRKKRwFxGJQoWGu5klmtl8M1tiZivM7O4CxpxpZnvNbHFourN0yhURkXCE84VqNnCWux8wswQg3czedPe5+cZ95O4XRb5EEREpqkLDPfTw6wOhtwmhyUuzKBERKZmwzrmbWbyZLQa2A++4+7wChvUJnbp508w6RLJIEREpmrDC3d1z3b0rkAz0MrP8TYgXAc3cvQswDphR0HbMbKSZZZhZxo4dO4pftYiInFCRrpZx9z3Af4Hz8s3f5+4HQq/fABLMrH4B609y9xR3T0lKSip20SIi5VlZPIyjMOFcLZNkZnVCr6sC5wCr841paKFHdZtZr9B2S95aTUSkFB05mMaR7WdyZGvbvD8PpkVku2XxMI7ChHO1TCPgGTOLJy+0X3b3/5jZaAB3nwgMBm40s8PAN8CQ0BexIiLl0pGDabDvDiArNGMz7LuDI0BctQEl2nZZPIyjMOFcLbMU6FbA/IlHvR4PjI9saSIipejAg3wX7N/JyptfwnAvD3SHqojEpiNbija/glG4i0hsimtUtPkVjMJdRGJTjV8DiflmJobmV3wKdxGJSXHVBkCteyGuMWB5f9a6t8RfpkLZPIyjMHpYh4jErLhqA0rly9OyeBhHYXTkLiIShRTuIiJRSOEuIlElWu6fLOnPoXAXkaiRmJjIrl27KnzAuzu7du0iMTH/1Tzh0xeqIhI1kpOTyczMJBq6ziYmJpKcnFzs9RXuIhI1EhISaNGiRdBllAs6LSMiEoUU7iIiUUjhLiIShRTuIiJRSOEuIhKFFO4iIlFI4S4iEoV0nbtIOeJ+BLJm4AdfBD8Eif2x6sMwK/6dihWVey7+zTQ4+DKQC1UvxqoNxaxy0KVVCIWGu+X9rfoQqBIaP9Xd78o3xoB/AxcAB4Fr3H1R5MsViW6+93eQ9TZ5z5kHDqzHs96Aei9hFlvHYr7nF5Cdznefxf51eNZbUPd5zHTSoTDhfELZwFnu3gXoCpxnZr3zjTkfaB2aRgKPFLbRw7ll1/vhvPPOo06dOlx00UWlup933nmHHj160KlTJ3r06MH7779fpPWzsrLo1asXXbp0oUOHDtx1112FrxSGWbNm0bZtW1q1asX9998fkW1K5HnOZ5D1Ft+FGQBZkLsOst8LqqxAeM6yHwY7AFlweCUcSg+qrAql0HD3PAdCbxNCU/5kHgg8Gxo7F6hjZid8EOFn2/ez8Ivdxam5yG699Vaee+65sMc3b968WPupX78+M2fOZNmyZTzzzDNcddVVRVq/SpUqvP/++yxZsoTFixcza9Ys5s6dW6xavpWbm8uYMWN48803WblyJVOmTGHlypUl2qaUkpyFBc/3g3j2nLKtJWiHMoDDx873g3j2vDIvpyIK6/82ZhZvZouB7cA77p7/020CbDzqfWZoXv7tjDSzDDPL8CNHGDppLi9nbMw/rFgWLFhA586dycrK4uuvv6ZDhw4sX74cgLPPPpuaNWtGZD8A06dP55xzzsHd2bJlC23atGHr1q1069aNxo0bA9ChQweysrLIzs4Oe7tmRo0aNQDIyckhJyeHvDNexTd//nxatWpFy5YtqVy5MkOGDOG1114r0TallMTVA4svYEFliD+5zMsJVFx9KPDceiIWa59FMYUV7u6e6+5dgWSgl5l1zDekoAQ65ryLu09y9xR3T2nbqDa9WtTltqlL+XPaCnJyjxS5+KP17NmTAQMGcMcdd3Dbbbdx5ZVX0rFj/jIjY9CgQTRs2JAJEyZwww03cPfdd9OwYcMfjJk2bRrdunWjSpUqRdp2bm4uXbt2pUGDBpx77rmcfvrpx4yZPHkyXbt2PWYaPHjwMWM3bdpE06ZNv3ufnJzMpk2bilSTlJEqPybvq638/5zisaqXBFBQgBLPAQr4RWdxULV0T69GiyJ9Q+Pue8zsv8B5wPKjFmUCTY96nwxsPtG24uOMp0f05G9vruaJ9M9Zs3U/E4Z1p2714n8Tfuedd9KzZ08SExN56KGHirTufffdxyuvvALA5s2b6dq1KwCpqalMmDDhmPHjxo2jY8eO9O7dm6FDh/5g2YoVK/jd737H22+/XeSfIT4+nsWLF7Nnzx4GDRrE8uXLj/klNWzYMIYNGxbW9grqa13S/w1I6TCrDPWex3ffCLnbwQwsEav9IBbfsPANRBGzqlD3WXz3GPCvAAOrjtX5FxZXN+jyKoRwrpZJAnJCwV4VOAf4e75hacBYM3sROB3Y6+5bCt15fBx/uqg97RvV4g/TlzFgfDqPDU/htEa1ivGjwFdffcWBAwfIyckhKyuL6tWrh73u7bffzu233w7knXNfvHjxCcdv2rSJuLg4tm3bxpEjR4iLy/tPUGZmJoMGDeLZZ5/l1FNPPWa9efPmMWrUKADuueceBgwo+OG8derU4cwzz2TWrFnHhPvkyZN54IEHjlmnVatWTJ069QfzkpOT2bjx+1NfmZmZ3506kvLHKrWC+m9D7vq8SyErtcEKPFUT/SyhPSS9n/eFsh8OfRa6SiZs7n7CCegMfAIsJe9o/c7Q/NHA6NBrAyYA64BlQEph2+3Ro4cf7ZMvd3uv+97xdne86W8s3ezF0b9/f588ebLfe++9PmbMmB8s++CDD/zCCy8MazvNmjU74fKcnBxPSUnxDz/80K+//np/4IEH3N199+7d3rlzZ586dWqx6t++fbvv3r3b3d0PHjzo/fr185kzZxZrW0fX2qJFC1+/fr1nZ2d7586dffny5SXapogEB8jwQvLV3QsP99Ka8oe7u/u2vd/4xRPSvdnv/uP/eGu15+YeCfsHfuaZZ3zQoEHu7n748GHv1auXv/fee+7u3q9fP69fv74nJiZ6kyZNfNasWSfcVmHhfvfdd/stt9zi7u779u3ztm3b+sqVK/0vf/mLV6tWzbt06fLdtG3btrB/hiVLlnjXrl29U6dO3qFDB7/77rvDXvdEXn/9dW/durW3bNnS77333ohsU0SCEW64mwf0rMGUlBTPyMg4Zn724Vz+NGM5L2dkcs5pJ/PPn3ehZmJCABWKiJQ/ZrbQ3VMKG1fuTmBVqRTP3y/tzN0DOvDBmu1c8vAcNuz8OuiyREQqlHIX7pB3NcfVfZvz3LW92HkgmwHj0/nfpxX/gbciImWlXIb7t/q2qk/a2H40rlOVEU/N57EP1xd4aZ+IiPxQuQ53gKZ1qzHtxr78rEND7ntjFb9+eQlZOblBlyUiUq6V+3AHqF6lEg8P685vzm3D9E82cfmjH7Nl7zeFrygiEqMqRLhD3nn4m89uzWPDU1i/42v6j5tNxoavgi5LRKRcqjDh/q1z25/M9Jv6UqNKPEMfm8uL878MuiQRkXKnwoU7QOuTa/LamH70blmP37+6jDtfW17ixmMiItGkQoY7QO1qCTw9ohejzmjJsx9/wZWPz2PXgfDb64qIRLMKG+6Q11nyDxecxj9/3oVPNu5hwPjZrNi8N+iyREQCV6HD/VuDuiUzdXQfjrhz6SNz+M/SE3YbFhGJelER7gCdk+vw2thUOjSuzdgXPuGBt1Zz5IhueBKR2BQ14Q7QoGYiL9xwOkN6NmXCB+u44dkM9mXlBF2WiEiZi6pwh7zGY3+7pBN/GdiB/326g4snzGb9jgOFrygiEkWiLtwh74anq/o05/nrT2fPwRwGTpjNB2u2B12WiEiZicpw/1bvlvVIG5tK8knVuPbpBUz83zo1HhORmBDV4Q6QfFI1pt3Yhws6NeL+N1fzyxcX880hNR4TkehWaLibWVMz+8DMVpnZCjP7ZQFjzjSzvWa2ODTdWTrlFk+1ypUYP7Qbt/6sLTOXbuayR+ewaY8aj4lI9ArnyP0w8Bt3Pw3oDYwxs/YFjPvI3buGpnsiWmUEmBljftKKx4ensGHnQQaOT2f+52o8JiLRqdBwd/ct7r4o9Ho/sApoUtqFlZazTzuZGWNSqZWYwBWPzWXyvC+CLklEJOKKdM7dzJoD3YB5BSzuY2ZLzOxNM+twnPVHmlmGmWXs2BHcY/NaNajB9DGp9Gtdn9unL+f26cs4dFiNx0QkeoQd7mZWA5gG/Mrd9+VbvAho5u5dgHHAjIK24e6T3D3F3VOSkpKKWXJk1K6awBNX92T0j09l8rwvufLxeexU4zERiRJhhbuZJZAX7JPd/dX8y919n7sfCL1+A0gws/oRrbQUxMcZvz+/Hf8e0pUlmXsYMC6d5ZvUeExEKr5wrpYx4Alglbs/eJwxDUPjMLNeoe3uimShpWlg1yZMu7EvAIMnziFtiRqPiUjFFs6ReypwFXDWUZc6XmBmo81sdGjMYGC5mS0BHgKGeAW7W6hjk9qk3dyPTk1q84spn3D/m6vJVeMxEamgLKgMTklJ8YyMjED2fSKHDh/h7pkrmDzvS85sm8S/h3SjdtWEoMsSEQHAzBa6e0ph46L+DtWiqlwpjvsGdeLeizuS/tlOBk2YzdrtajwmIhWLwv04ruzdjBdu6M3eb3IYNGE276/eFnRJIiJhU7ifQK8WdUm7uR/N6lfjumcymPDBWjUeE5EKQeFeiCZ1qvLKqL7079yYB95aw81TPuHgocNBlyUickIK9zBUrRzPv4d05ffnt+P1ZVsY/MjHZO4+GHRZIiLHpXAPk5kx+sen8uTVPdm4+yADxs9m7voKcym/iMQYhXsR/aRdA14bk0qdaglc+fg8npv7hc7Di0i5o3AvhpZJNZgxJpUz2iTxpxnL+aMaj4lIOaNwL6ZaiQk8NjyFMT85lSnzN3LFY3PZsV+Nx0SkfFC4l0B8nHHrz9oxbmg3lm/ey4Dx6SzN3BN0WSIiCvdI6N+lMdNu7EucGZdN/JgZn2wKuiQRiXEK9wjp0Lg2aWNT6dK0Dr96aTF/fWOVGo+JSGAU7hFUr0YVJl9/OsP7NGPSh+sZ8fQC9h7MCbosEYlBCvcIS4iP456BHfnbJZ34eN1OBk5I57Nt+4MuS0RijMK9lAztdQpTbujNgexcBj08h3dXqvGYiJQdhXspSmlel7SxqbSoX50bnstg/Puf6YYnESkTCvdS1rhOVV4Z3YeBXRrzf29/ypgXFvF1thqPiUjpUriXgcSEeP7586788YJ2zFq+lUsfmcPGr9R4TERKTzgPyG5qZh+Y2SozW2FmvyxgjJnZQ2a21syWmln30im34jIzRp5xKk+N6MXmPd8wYHw6c9btDLosEYlS4Ry5HwZ+4+6nAb2BMWbWPt+Y84HWoWkk8EhEq4wiP26TxGtj+1GvRhWuemI+T8/+XOfhRSTiCg13d9/i7otCr/cDq4Am+YYNBJ71PHOBOmbWKOLVRokW9asz/aa+/KRtEn+euZLfTVtK9uHcoMsSkShSpHPuZtYc6AbMy7eoCbDxqPeZHPsLADMbaWYZZpaxY8eOIpYaXWomJjDpqhR+cVYrXs7IZOikuWzflxV0WSISJcIOdzOrAUwDfuXu+/IvLmCVY841uPskd09x95SkpKSiVRqF4uKMX/+0LQ8P686qLfvpPz6dxRv3BF2WiESBsMLdzBLIC/bJ7v5qAUMygaZHvU8GNpe8vNhwQadGTLuxLwnxcVz+6MdMW5gZdEkiUsGFc7WMAU8Aq9z9weMMSwOGh66a6Q3sdfctEawz6rVvXIu0sf3occpJ/OaVJdz7n5UcztUDQESkeCqFMSYVuApYZmaLQ/P+CJwC4O4TgTeAC4C1wEFgRMQrjQF1q1fm2et6cd/rq3g8/XPWbNvPuKHdqFOtctCliUgFY0FdhpeSkuIZGRmB7LsieHnBRu6YsZyGtRN5/OoU2pxcM+iSRKQcMLOF7p5S2DjdoVpOXd6zKVNG9uabnFwGTZjNWyu2Bl2SiFQgCvdyrEezk5g5th+tGtRg1HML+fe7n3FEDwARkTAo3Mu5hrUTeWlUHy7p3oR/vvspN01W4zERKZzCvQJITIjnH5d14U8XteftlVu55OE5fLlLjcdE5PgU7hWEmXFdvxY8c20vtu7LYsCEdGavVeMxESmYwr2C+VHrJNLGptKgZhWGPzmfJ9PVeExEjqVwr4Ca1avOqzelcna7Btzzn5XcOnUpWTlqPCYi31O4V1A1qlRi4pU9+OXZrZm6MJMhk+ayTY3HRCRE4V6BxcUZt5zbholXdufTbfvpPy6dRV/uDrosESkHFO5R4LyOjXj1pr5USYhjyKNzeSVjY+EriUhUU7hHiXYNa5E2ph89W5zErVOXcvfMFWo8JhLDFO5R5KTqlXlmRC+uTW3BU7M3MPzJ+ez++lDQZYlIABTuUaZSfBx39m/PA4M7k7FhNwMmpLN6a/5nq4hItFO4R6nLUpry0qjeZOcc4ZKH5zBrudrri8QShXsU63bKScy8uR9tTq7J6OcX8eA7n6rxmEiMULhHuZNrJfLiyN4M7pHMQ+99xqjnF3JAjcdEop7CPQYkJsTzwODO3NW/Pe+v3s4lD89mw86vgy5LREqRwj1GmBkjUlvw7LW92L4/mwHj0/nw0x1BlyUipSScB2Q/aWbbzWz5cZafaWZ7zWxxaLoz8mVKpKS2qk/amH40rlOVa56az+MfrVfjMZEoFM6R+9PAeYWM+cjdu4ame0pelpSmU+pVY9qNfflp+4bc+/oqfvPyEjUeE4kyhYa7u38IfFUGtUgZql6lEg8P686vz23Dq59s4uePfszWvWo8JhItInXOvY+ZLTGzN82sw/EGmdlIM8sws4wdO3S+N2hxccYvzm7NpKt6sHb7AfqPT2fhF2o8JhINIhHui4Bm7t4FGAfMON5Ad5/k7inunpKUlBSBXUsk/LRDQ6aPSaVa5XiGTprLSwu+DLokESmhEoe7u+9z9wOh128ACWZWv8SVSZlqc3JNXhuTyukt6/K7acu467Xl5KjxmEiFVeJwN7OGZmah171C29xV0u1K2atTrTJPXdOTG37Ugmc+/oKrnpjHV2o8JlIhhXMp5BTgY6CtmWWa2XVmNtrMRoeGDAaWm9kS4CFgiOvaugqrUnwct1/Yngcv78KiL/cwYHw6Kzer8ZhIRWNB5XBKSopnZGQEsm8Jz5KNexj13EL2fpPD/13WhQs7Nwq6JJGYZ2YL3T2lsHG6Q1WOq0vTOqTdnMppjWoy5oVF/OPtNWo8JlJBKNzlhBrUTGTKyN78PKUp495fy8jnMtiflRN0WSJSCIW7FKpKpXjuv7QT9wzswAdrdjDo4Tl8rsZjIuWawl3CYmYM79Oc5687nV0Hshk4Pp3/qfGYSLmlcJci6XNqPdLG5jUeG/HUfB793zo1HhMphxTuUmRN61bj1Zv6cn7HRvztzdX86qXFajwmUs4o3KVYqlWuxPgrunHrz9qStmQzl038mM17vgm6LBEJUbhLsZkZY37SiseuSuHznV8zYHw6CzaogahIeaBwlxI7p/3JzBjTl5qJCVzx2FymzFfjMZGgKdwlIlo1qMmMm1Lpc2p9/vDqMu6YsYxDh9V4TCQoCneJmNrVEnjqmp6MOqMlz8/9kiufmMfOA9lBlyUSkxTuElHxccYfLjiNfw/pypKNexg4fjbLN+0NuiyRmKNwl1IxsGsTpo7uyxF3Bk+cw8wlm4MuSSSmKNyl1HRKrk3a2H50bFybm6d8wt9nrSZXjcdEyoTCXUpVUs0qvHBDb4b2OoVH/ruO659ZwD41HhMpdQp3KXWVK8Xxt0s6ce/FHfnos51cPGE263YcCLoskaimcJcyc2XvZky+/nT2Hszh4vGz+WD19qBLEolaCveAHc45TPY3sXO54Okt6/Ha2FSa1q3Gtc8s4JH/qvGYSGkI5xmqT5rZdjNbfpzlZmYPmdlaM1tqZt0jX2b0+Xrv1/z1in/Rv+ZVDKg1nNHdb+XTheuCLqtMJJ9UjWk39uXCTo34+6zV/OLFxXxzSI3HRCIpnCP3p4HzTrD8fKB1aBoJPFLysqLfHy/4K+nT53H40GGO5B5h3eIN/PasP7Mjc1fQpZWJqpXjGTe0G7ed15b/LN3M4Ilz2KTGYyIRU2i4u/uHwIm6QQ0EnvU8c4E6ZqYnKZ/A2sWfs27JF+RkH/7B/MPZh5n5yFsBVVX2zIybzmzFk1f35MtdBxkwLp1562Pjl5tIaYvEOfcmwMaj3meG5h3DzEaaWYaZZezYEbtP8dm8divxlY796HMOHebzZbHXdOsn7RowY2wqtasmMOzxeTw/94ugSxKp8CIR7lbAvAK/IXP3Se6e4u4pSUlJEdh1xdSyczMOF/Bwi8pVK3NanzYBVBS8U5NqMH1MKj9qXZ87Ziznj9PVeEykJCIR7plA06PeJwO61/wEkts0JuWnXahctfJ38+LijMRqVbho5LkBVhas2lUTePzqntx05qm8MO9Lhj0+lx37Y+dKIpFIikS4pwHDQ1fN9Ab2uvuWCGw3qt3x0i1c/tsB1GlQm6o1Ekkd1IsJC+6nVr2aQZcWqPg447bz2vHQ0G4s27SXAePTWZapxmMiRWWFXWNsZlOAM4H6wDbgLiABwN0nmpkB48m7ouYgMMLdMwrbcUpKimdkFDpMYtjyTXsZ9dxCdh7I5v8N7szArgV+lSMSU8xsobunFDouqBtIFO4Sjp0Hsrnp+UXM3/AVo37cktt+1o74uIK+5hGJDeGGu+5QlXKtfo0qPH/96VzZ+xQe/d96rn16AXsPqvGYSGEU7lLuVa4Ux70Xd+KvgzoxZ91OLn54Nmu37w+6LJFyTeEuFcYVp5/CCzf0Zn9WDhdPmMN7q7YFXZJIuaVwlwqlZ/O6pI3tR/P61bj+2QwmfLBWjcdECqBwlwqncZ2qvDKqLwO6NOaBt9Yw9oVPOHjocOErisQQhbtUSFUrx/Ovn3flD+e3443lW7j0kY/Z+NXBoMsSKTcU7lJhmRmjfnwqT13Tk8zdBxk4YTYfr1PjMRFQuEsUOLNtA14bk8pJ1RK48ol5PPvxBp2Hl5incJeo0DKpBjPGpHJmmyTufG0Ff3h1GdmH9QAQiV0Kd4kaNRMTeGx4CmN/0ooXF2zkisfmsX1/VtBliQRC4S5RJS7O+O3P2jLhiu6s3LyPAeNms2TjnqDLEilzCneJShd2bsS0G/sSH2dc9ujHTP8kM+iSRMqUwl2iVvvGtUgbm0r3U+pwy0tLuO/1lRzO1QNAJDYo3CWq1atRheeuO52r+zTjsY8+Z4Qaj0mMULhL1EuIj+PugR25/5JOzF2/i4ET0vlsmxqPSXRTuEvMGNLrFF4c2ZsD2blcPGE2b6/YGnRJIqVG4S4xpUezusy8OZVTG9Rg5HMLeei9zzhyRDc8SfRRuEvMaVS7Ki+P6sOgbk148J1PGfPCIr7OVuMxiS5hhbuZnWdma8xsrZn9voDlZ5rZXjNbHJrujHypIpGTmBDPg5d34Y4LT+OtFVu59JE5ajwmUaXQcDezeGACcD7QHhhqZu0LGPqRu3cNTfdEuE6RiDMzrv9RS54e0YvNe76h//h05qzdGXRZIhERzpF7L2Ctu69390PAi8DA0i1LpOyc0SaJtLH9SKpRhauenM/Tsz9X4zGp8MIJ9ybAxqPeZ4bm5dfHzJaY2Ztm1iEi1YmUkeb1qzN9TCpntWvAn2eu5LapS9V4TCq0cMLdCpiX/7BmEdDM3bsA44AZBW7IbKSZZZhZxo4dO4pUqEhpq1GlEo9e2YNfnN2aVxZmMmTSXLbvU+MxqZjCCfdMoOlR75OBzUcPcPd97n4g9PoNIMHM6uffkLtPcvcUd09JSkoqQdkipSMuzvj1uW14ZFh31mzdT//x6SxW4zGpgMIJ9wVAazNrYWaVgSFA2tEDzKyhmVnoda/QdvVIHKmwzu+U13gsIT6Oyx/9mKkL1XhMKpZCw93dDwNjgbeAVcDL7r7CzEab2ejQsMHAcjNbAjwEDHF9IyUV3GmNapE2th8pzU7it68s4Z6ZajwmFYcFlcEpKSmekZERyL5FiuJw7hHue2MVT83eQGqreowf2p2TqlcOuiyJUWa20N1TChunO1RFClEpPo67+nfg/w3uzILPdzNwwmzWbFXjMSnfFO4iYbo8pSkvjupNVk4ugx6ezazlajwm5ZfCXaQIup9yEjNv7kfrk2sy+vmF/OvdT9V4TMolhbtIEZ1cK5GXRvbm0u7J/Ovdzxj9/EIOqPGYlDMKd5FiSEyI5/8u68yfLmrPe6u3c8nDs/li19dBlyXyHYW7SDGZGdf1a8EzI3qxbV82A8bPJv0zNR6T8kHhLlJC/VrXJ21sKifXqsLwJ+fx+Efr1XhMAqdwF4mAZvWq8+pNqZzb/mTufX0Vv3llCVk5ajwmwVG4i0RIjSqVeGRYD245pw2vLtrEzyfNZeteNR6TYCjcRSIoLs745TmtefSqHqzdltd4bOEXu4MuS2KQwl2kFPysQ0NevSmVqgnxDJ00l5czNha+kkgEKdxFSknbhjVJG5tKrxZ1uW3qUv6ctoIcNR6TMqJwFylFdapV5ukRPbmuXwuenrOB4U/M56uvDwVdlsQAhbtIKasUH8efLmrPPy7rwsIvdzNgfDqrtuwLuiyJcgp3kTJyaY9kXh7Vh5zcI1zy8BzeXLYl6JIkiincRcpQ16Z1mDm2H+0a1eTGyYt48O01ajwmpULhLlLGGtRK5MWRvbk8JZmH3l/LyOcWsj8rJ+iyJMoo3EUCUKVSPH+/tDN3D+jAB2u2c8nDc9iwU43HJHIU7iIBMTOu7tuc567txc4D2QwYn87/Pt0RdFkSJcIKdzM7z8zWmNlaM/t9AcvNzB4KLV9qZt0jX6pIdOrbqj5pY/vRuE5VRjw1n8c+VOMxKblCw93M4oEJwPlAe2CombXPN+x8oHVoGgk8EuE6RaJa07rVmHZjX37WoSH3vbGKX7+sxmNSMuEcufcC1rr7enc/BLwIDMw3ZiDwrOeZC9Qxs0YRrlUkqlWvUomHh3XnN+e2YfoneY3HdEerFFelMMY0AY5ujJEJnB7GmCbADy7kNbOR5B3ZA2Sb2fIiVRu96gN6ykMefRYhX0D9ymP1WYTo78X32oYzKJxwtwLm5T8hGM4Y3H0SMAnAzDLcPSWM/Uc9fRbf02fxPX0W39Nn8T0zywhnXDinZTKBpke9TwY2F2OMiIiUkXDCfQHQ2sxamFllYAiQlm9MGjA8dNVMb2Cvu+veahGRgBR6WsbdD5vZWOAtIB540t1XmNno0PKJwBvABcBa4CAwIox9Typ21dFHn8X39Fl8T5/F9/RZfC+sz8J0Pa2ISPTRHaoiIlFI4S4iEoUCCffC2hnECjN70sy263p/MLOmZvaBma0ysxVm9sugawqKmSWa2XwzWxL6LO4OuqYgmVm8mX1iZv8JupagmdkGM1tmZosLuySyzM+5h9oZfAqcS94llAuAoe6+skwLKQfM7AzgAHl393YMup4ghe5obuTui8ysJrAQuDhG/14YUN3dD5hZApAO/DJ093fMMbNfAylALXe/KOh6gmRmG4AUdy/0hq4gjtzDaWcQE9z9Q+CroOsoD9x9i7svCr3eD6wi7y7nmBNq43Eg9DYhNMXklQ9mlgxcCDwedC0VTRDhfrxWBSIAmFlzoBswL+BSAhM6FbEY2A684+6x+ln8C7gNUJOdPA68bWYLQ+1cjiuIcA+rVYHEJjOrAUwDfuXuMfsUaXfPdfeu5N3t3cvMYu60nZldBGx394VB11KOpLp7d/I68Y4JndotUBDhrlYFUqDQ+eVpwGR3fzXoesoDd98D/Bc4L9hKApEKDAidZ34ROMvMng+2pGC5++bQn9uB6eSd5i5QEOEeTjsDiTGhLxGfAFa5+4NB1xMkM0syszqh11WBc4DVgRYVAHf/g7snu3tz8nLifXe/MuCyAmNm1UMXG2Bm1YGfAse90q7Mw93dDwPftjNYBbzs7ivKuo7ywMymAB8Dbc0s08yuC7qmAKUCV5F3dLY4NF0QdFEBaQR8YGZLyTsYesfdY/4yQOFkIN3MlgDzgdfdfdbxBqv9gIhIFNIdqiIiUUjhLiIShRTuIiJRSOEuIhKFFO4iIlFI4S4iEoUU7iIiUej/AzcDfobkQH1KAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "X = np.array([[3, 3], [4, 3], [1, 1]])\n",
    "Y = np.array([1, 1, -1])\n",
    "model = Perceptron(X, Y, lr=1)\n",
    "weight, b = model.fit()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题2.3\n",
    "&emsp;&emsp;证明以下定理：样本集线性可分的充分必要条件是正实例点所构成的凸壳与负实例点所构成的凸壳互不相交。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**\n",
    "\n",
    "**解答思路：**\n",
    "1. 写出凸壳和线性可分的定义\n",
    "2. 证明充分性：线性可分$\\Rightarrow$凸壳不相交  \n",
    "3. 证明必要性：凸壳不相交$\\Rightarrow$线性可分  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：凸壳与线性可分的定义**  \n",
    "1. 根据书中第47页脚注1的凸壳定义如下：  \n",
    "> 设集合$S \\subset R^n$，是由$R^n$中的$k$个点所组成的集合，即$S=\\{x_1,x_2,\\cdots, x_k\\}$。定义$S$的凸壳$\\text{conv}(S)$为：\n",
    "> $$\n",
    "\\text{conv}(S) = \\left\\{ x = \\sum_{i=1}^k \\lambda_i x_i \\Big| \\sum_{i=1}^k \\lambda_i=1,\\lambda_i \\geqslant 0, i=1,2,\\cdots, k \\right\\}\n",
    "$$\n",
    "\n",
    "2. 根据书中第36页的线性可分定义如下： \n",
    "> 给定一个数据集\n",
    "> $$\n",
    "T=\\{(x_1,y_1), (x_2,y_2), \\cdots, (x_n,y_n)\\}\n",
    "$$\n",
    "> 其中$x_i \\in \\mathcal{X}=R_n, y_i \\in \\mathcal{Y} = \\{+1, -1\\}, i=1,2,\\cdots, n$，如果存在某个超平面$S$\n",
    "> $$\n",
    "w \\cdot x + b = 0\n",
    "$$\n",
    "> 能够将数据集的正实例点和负实例点完全正确划分到超平面的两侧，即对所有$y_i=+1$的实例$i$，有$w \\cdot x_i + b > 0$，对$y_i = -1$的实例$i$，有$w \\cdot x_i + b < 0$，则称数据集$T$为线性可分数据集，否则称数据集$T$线性不可分。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：证明充分性：线性可分$\\Rightarrow$凸壳不相交**  \n",
    "\n",
    "证明思路：\n",
    "1. 条件假设：将数据集分为正实例的凸壳（正凸壳）、负实例的凸壳（负凸壳），并列出相关性质；\n",
    "2. 采用反证法，即凸壳相交，假设一个点同时存在于正负两个凸壳中；\n",
    "3. 按照步骤1得到的性质，不能同时满足正负实例点的条件，得出矛盾。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "证明步骤：\n",
    "1. 条件假设：  \n",
    "&emsp;&emsp;假设数据集$T$中的正例点集为$S_+$，$S_+$的凸壳为$\\text{conv}(S_+)$，负实例点集为$S_-$，$S_-$的凸壳为$\\text{conv}(S_-)$。  \n",
    "&emsp;&emsp;若数据集$T$是线性可分的，根据线性可分的定义，则存在一个超平面\n",
    "$$\n",
    "w \\cdot x + b = 0\n",
    "$$\n",
    "能够将$S_+$和$S_-$完全分离。  \n",
    "&emsp;&emsp;对于所有的正例点$x_i$，有\n",
    "$$\n",
    "w \\cdot x_i + b = \\varepsilon_i > 0, \\quad i = 1,2,\\cdots,|S_+|\n",
    "$$\n",
    "&emsp;&emsp;根据凸壳的定义，对于$\\text{conv}(S_+)$中的元素$s^+$，有\n",
    "$$\n",
    "\\begin{aligned}\n",
    "w \\cdot s^+ &= w \\cdot \\sum_{i=1}^k \\lambda_i x_i \\\\\n",
    "&= \\sum_{i=1}^k \\lambda_i(\\varepsilon_i - b) \\\\\n",
    "&= \\sum_{i=1}^k \\lambda_i \\varepsilon_i - \\sum_{i=1}^k \\lambda_i b \\quad (\\because \\sum_{i=1}^k \\lambda_i = 1) \\\\\n",
    "& = \\sum_{i=1}^k \\lambda_i \\varepsilon_i - b \n",
    "\\end{aligned}\n",
    "$$\n",
    "&emsp;&emsp;因此$\\displaystyle w \\cdot s^+ + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i > 0$。  \n",
    "&emsp;&emsp;同理对于$S_-$中的元素$s^-$，有$\\displaystyle w \\cdot s^- + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i < 0$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 反证法：  \n",
    "&emsp;&emsp;假设$\\text{conv}(S_+)$和$\\text{conv}(S_-)$相交，即存在某个元素$s$，同时满足$s \\in \\text{conv}(S_+)$和$s \\in \\text{conv}(S_-)$。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. 根据步骤1得到的性质：  \n",
    "&emsp;&emsp;有$\\displaystyle w \\cdot s + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i > 0$且$\\displaystyle w \\cdot s + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i < 0$，可推出矛盾。  \n",
    "&emsp;&emsp;因此，$\\text{conv}(S_+)$ 和$\\text{conv}(S_-)$必不相交，充分性得证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第3步：证明必要性：凸壳不相交$\\Rightarrow$线性可分**  \n",
    "\n",
    "证明思路：\n",
    "1. 条件假设：将数据集分为正实例的凸壳（正凸壳）、负实例的凸壳（负凸壳），并定义两个凸壳的距离：分别处于两个凸壳集合中的点的距离最小值，即为凸壳边界上的最近两点之间的距离\n",
    "2. 计算两点的法线方程参数$w$和$b$\n",
    "3. 根据线性可分正负实例点的条件，可得到该法线是分离超平面，即满足线性可分条件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "证明步骤：\n",
    "1. 条件假设：  \n",
    "&emsp;&emsp;假设数据集$T$中的正例点集为$S_+$，$S_+$的凸壳为$\\text{conv}(S_+)$，负实例点集为$S_-$，$S_-$的凸壳为$\\text{conv}(S_-)$，且$\\text{conv}(S_+)$与$\\text{conv}(S_-)$不相交。   \n",
    "&emsp;&emsp;定义两个点$x_1,x_2$的距离为\n",
    "$$\n",
    "\\text{dist}(x_1,x_2) = \\|x_1 - x_2\\|_2 = \\sqrt{(x_1 - x_2)^2}\n",
    "$$  \n",
    "&emsp;&emsp;定义$\\text{conv}(S_+)$、$\\text{conv}(S_-)$的距离，分别处于两个凸壳集合中的点的距离最小值，即为分别处于两个凸壳边界上的最近两点之间的距离：\n",
    "$$\n",
    "\\text{dist}(\\text{conv}(S_+),\\text{conv}(S_-)) = \\min \\|s_+ - s_-\\|_2 = \\text{dist}(s_+, s_-), \\quad s_+ \\in \\text{conv}(S_+), s_- \\in \\text{conv}(S_-)\n",
    "$$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 计算两点的法线方程参数$w$和$b$  \n",
    "&emsp;&emsp;假设$x_+ \\in \\text{conv}(S_+), x_- \\in \\text{conv}(S_-)$，根据步骤1，可得：$$\n",
    "\\text{dist}(x_+, x_-) = \\text{dist}(\\text{conv}(S_+),\\text{conv}(S_-))\n",
    "$$\n",
    "&emsp;&emsp;该两点$(x_+, x_-)$之间存在一条法线，法线方程$w \\cdot x + b = 0$的参数如下：\n",
    "$$\n",
    "\\left \\{ \\begin{array}{ll} \n",
    "w = x_+ - x_- \\\\ \n",
    "\\displaystyle b = -\\frac{1}{2}(x_+^2 -  x_-^2)\n",
    "\\end{array}\\right .\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. 根据正负实例点的条件证明：  \n",
    "&emsp;&emsp;对于任意正实例点$x \\neq x_+$，都有$\\text{dist}(x,x_-) \\geqslant \\text{dist}(x , x_+)$，即点$x$与正凸壳边界上的正例点距离大于与负凸壳边界上的负例点距离，有\n",
    "$$\n",
    "\\begin{aligned}\n",
    "w\\cdot x +b & = (x_+-x_-)\\cdot x -\\frac{1}{2}(x_+^2 -  x_-^2) \\\\\n",
    "& = \\frac{1}{2} [2x(x_+ - x_-) - (x_+^2 -  x_-^2)] \\\\\n",
    "&= \\frac{1}{2} (x_-^2 - 2 x x_- - x_+^2 + 2 x x_+) \\\\\n",
    "&= \\frac{1}{2} [(x_-^2 - 2 x x_- + x^2) - (x_+^2 - 2 x x_+ + x^2)] \\\\\n",
    "&= \\frac{1}{2}(\\|x_- - x\\|_2^2-\\|x_+ - x\\|_2^2)\\\\\n",
    "&= \\frac{1}{2}[\\text{dist}(x,x_-)^2-\\text{dist}(x,x_+)^2]\n",
    "\\end{aligned}\n",
    "$$\n",
    "&emsp;&emsp;根据$\\text{dist}(x,x_-) \\geqslant \\text{dist}(x , x_+)$，则\n",
    "$$\n",
    "w\\cdot x +b = \\frac{1}{2}[\\text{dist}(x,x_-)^2-\\text{dist}(x,x_+)^2] \\geqslant 0\n",
    "$$\n",
    "&emsp;&emsp;综上所述，对于任意正实例点$x \\neq x_+$，都有$w\\cdot x +b \\geqslant 0$。  \n",
    "&emsp;&emsp;同理，对于任意负实例点$x \\neq x_-$，都有$\\text{dist}(x,x_+) \\geqslant \\text{dist}(x , x_-)$，可得$w\\cdot x +b \\leqslant 0$。  \n",
    "\n",
    "  &emsp;&emsp;根据线性可分条件，对所有正实例$x_i$，有$w \\cdot x_i + b > 0$，对所有负实例$x_i$，有$w \\cdot x_i + b < 0$，则称数据集$T$为线性可分数据集，该法线为分离超平面，必要性得证。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.11"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
